package com.lw.leetcode.bingChaJi.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * bingchaji
 * 721. 账户合并
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/19 10:30
 */
public class AccountsMerge {


    public static void main(String[] args) {
        AccountsMerge test = new AccountsMerge();

        //  [["Alex","Alex0@m.co","Alex4@m.co","Alex5@m.co"],
        //  ["Ethan","Ethan0@m.co","Ethan3@m.co"],
        //  ["Gabe","Gabe0@m.co","Gabe2@m.co","Gabe3@m.co","Gabe4@m.co"],
        //  ["Kevin","Kevin2@m.co","Kevin4@m.co"]]
        List<List<String>> accounts = new ArrayList<>();
        accounts.add(Arrays.asList("Alex", "Alex5@m.co", "Alex4@m.co", "Alex0@m.co"));
        accounts.add(Arrays.asList("Ethan", "Ethan3@m.co", "Ethan3@m.co", "Ethan0@m.co"));
        accounts.add(Arrays.asList("Kevin", "Kevin4@m.co", "Kevin2@m.co", "Kevin2@m.co"));
        accounts.add(Arrays.asList("Gabe", "Gabe0@m.co", "Gabe3@m.co", "Gabe2@m.co"));
        accounts.add(Arrays.asList("Gabe", "Gabe3@m.co", "Gabe4@m.co", "Gabe2@m.co"));

        List<List<String>> lists = test.accountsMerge(accounts);
        System.out.println(lists);
    }


    private Map<String, String> map = new HashMap<>();

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> names = new HashMap<>();
        Map<String, Set<String>> sets = new HashMap<>();
        for (List<String> account : accounts) {
            int size = account.size();
            String s = find(account.get(1));
            names.put(s, account.get(0));
            for (int i = 2; i < size; i++) {
                String s1 = find(account.get(i));
                if (!s.equals(s1)) {
                    map.put(s1, s);
                }
            }
        }
        Set<String> keySet = map.keySet();
        for (String s : keySet) {
            sets.computeIfAbsent(find(s), v -> new HashSet<>()).add(s);
        }
        List<List<String>> lists = new ArrayList<>();
        for (Map.Entry<String, Set<String>> entry : sets.entrySet()) {
            List<String> list = new ArrayList<>(entry.getValue().size() + 1);
            list.add(names.get(entry.getKey()));
            ArrayList<String> values = new ArrayList<>(entry.getValue());
            Collections.sort(values);
            list.addAll(values);
            lists.add(list);
        }
        return lists;
    }

    private String find(String key) {
        String value = map.get(key);
        if (value == null) {
            map.put(key, key);
            return key;
        }
        if (key.equals(value)) {
            return key;
        }
        String s = find(value);
        map.put(key, s);
        return s;
    }

}
